#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//递归
void FGSort(int* a, int left, int right)
{
	if (left == right)
		return;
	int middle = (left + right) / 2;

	FGSort(a, left, middle);
	FGSort(a, middle + 1, right);

	int begin1 = left,end1=middle;
	int begin2 = middle+1,end2=right;
	int tmp[10];
	int j = 0;
	while (begin1 <= end1 || begin2 <= end2)
	{
		if (begin1 > end1)
		{
			tmp[j] = a[begin2];
			j++;
			begin2++;
		}
		else if (begin2 > end2)
		{
			tmp[j] = a[begin1];
			j++;
			begin1++;
		}
		else if (a[begin1] < a[begin2])
		{
			tmp[j] = a[begin1];
			j++;
			begin1++;
		}
		else
		{
			tmp[j] = a[begin2];
			j++;
			begin2++;
		}

	}
	memcpy(a + left, tmp, sizeof(int) * j);
}

//非递归
void GSort(int *a,int left,int right)
{
	/*int midi = (left + right) / 2;*/
	int gap = 1;
	int* tmp = (int*)malloc(right*sizeof(int));
	int j = 0;
	while (gap <= right)
	{
		for (int i = 0; i <= right; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			j = 0;
			if (end1 >= right)
			{
				continue;
			}
			else if(end2>right)
			{
				end2 = right;
			}
			while (begin1 <= end1 || begin2 <= end2)
			{
				if (begin1 > end1)
				{
					*(tmp + j) = a[begin2];
					j++;
					begin2++;
				}
				else if (begin2 > end2)
				{
					*(tmp + j) = a[begin1];
					j++;
					begin1++;
				}
				else if (a[begin1] < a[begin2])
				{
					*(tmp + j) = a[begin1];
					j++;
					begin1++;
				}
				else
				{
					*(tmp + j) = a[begin2];
					j++;
					begin2++;
				}

			}
			memcpy(a+i, tmp, sizeof(int) * j);

		}
		gap *= 2;
	}
	for (int i = 0; i <=right; i++)
	{
		printf("%d ", a[i]);
	}
	
	free(*tmp);
}

int main()
{
	int a[] = { 6,7,8,2,1,5,9,3,0,11};
	//GSort(a, 0, sizeof(a) / sizeof(int) - 1);
	FGSort(a, 0, sizeof(a) / sizeof(int) - 1);
	return 0;
}